#include"bst.h"
#include<stdio.h>
#include<stdlib.h>

void BSTCreate(BinarySearchTree* t){
    t->root = NULL;
}

TreeNode* RemoveNode(BinarySearchTree* t,TreeNode*node,eleType value){
    if(node==NULL){
        return NULL;
    }
    if(value<node->val){
       node->left = RemoveNode(t,node->left,value);
    }else if(value>node->val){
        node->right = RemoveNode(t,node->right,value);
    }else{//找到了分四种情况
        if(node->left==NULL&&node->right==NULL){//叶子节点
            node->val = 0;
            free(node);
            node = NULL;
            return node;
        }else if(node->left==NULL){//如果有右儿子，但是没有左儿子   
            TreeNode* rightChild = node->right;
            free(node);
            node = rightChild;
            return node;
        }else if(node->right==NULL){
            TreeNode* leftChild = node->left;
            free(node);
            node = leftChild;
            return node;
        }else{//左右儿子
            TreeNode* replacement = node->right;
            while(replacement->left){
                replacement = replacement->left;
            }//找到该节点的右子树的最小值，就是右子树的最左边的
            node->val = replacement->val;
            node->right = RemoveNode(t,node->right,replacement->val);//找到了并替换了，现在不是父节点没有儿子，再次递归删一次就好了
            free(replacement);
            replacement = NULL;
        }
    }
   return node;
}

void BSTRemove(BinarySearchTree* t,eleType value){
    RemoveNode(t,t->root,value);
}

void BSTDestry(BinarySearchTree* t){
    while(t->root){
        BSTRemove(t,t->root->val);
    }
}

TreeNode* insertNode(BinarySearchTree*t,TreeNode* node,eleType value){
    if(node ==NULL){//如果这个递归遍历这个节点是空的，那么这个节点就是要插入的
        TreeNode* newNode = malloc(sizeof(TreeNode));
        newNode->val = value;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if(value>node->val){//要插入的值比当前递归遍历的节点大时
        node->right = insertNode(t,node->right,value);//继续递归右边
    }else if(value<node->val){
        node->left = insertNode(t,node->left,value);
    }
    return node;//返回传入的初始节点
}

void BSTInsert(BinarySearchTree*t,eleType value){
    t->root = insertNode(t,t->root,value);
}//实际外部调用插入节点函数 插入节点一定是从根节点开始的

bool searchNode(BinarySearchTree*t,TreeNode* node,eleType value){
    if(node==NULL){
        return false;
    }
    if(value<node->val){
        return searchNode(t, node->left, value);
    }else  if(value>node->val){
        return searchNode(t, node->right, value);
    }
    return true;
}

bool BSTSearch(BinarySearchTree*t,eleType value){
    return searchNode(t,t->root,value);
}

void inOrder(BinarySearchTree*t,TreeNode* node){
    if(node){
        inOrder(t,node->left);
        printf("%d ",node->val);
         inOrder(t,node->right);
    }
}

void BSTInorderTraversal(BinarySearchTree*t){
    inOrder(t,t->root);
    printf("\n");
}